1. Field of the Invention
The present invention relates to an operation unit and a program capable of reducing the size of a pre-calculated table needed when arithmetically masked data that is masked arithmetically is converted into logically masked data that is logically masked to have resistance to, for example, side channel analyses.
2. Description of the Related Art
Cryptography has become an indispensable technology for information communication technology in recent years. Such cryptography includes, for example, SSL (Secured Socket Layer), which is cryptography for communication, and an electronic signature capable of detecting whether a message is falsified. These technologies support a society that is becoming increasingly electronic as part of PKI (Public Key Infrastructure).
However, techniques for attacking cryptography are also becoming more sophisticated. Among others, a side channel analysis that measures the processing time or power consumption of an encryption processor to analyze secret information inside the encryption processor from measurement results increasingly poses an actual threat. The timing analysis and power analysis are known as typical side channel analyses.
As an example of the power analysis, the method of analyzing DES (Data Encryption Standard) will be described using drawings. This method is described in L. Goubin, J. Patarin, “DES and Differential Power Analysis—The Duplication Method”, CHES' 99, LNCS 1717, pp. 158-172, 1999.
FIG. 7 is a schematic diagram of a data conversion unit in the final 16-th stage in a DES cryptographic device.
When two pieces of 32-bit input data L15, R15 and 48-bit key data K16 are input into the 16-th data conversion unit, data conversion processing is performed and then, two pieces of 32-bit output data L16, R16 are output.
A result of bit transposition IP−1 of the output data L16, R16 becomes cipher text output from the DES cryptographic device. The cipher text and the bit transposition are each known to potential attackers and thus, the output data L16, R16 are also known to potential attackers.
The 16-th data conversion unit extends the 32-bit input data R15 to 48-bit data by E transposition. The extended data is used for XOR with the 48-bit key data K16. The 48-bit data obtained after the XOR is divided into eight pieces of 6-bit divided data and each piece of the divided data is input into S-boxes S1, S2, . . . , S8.
Six-bit data is input into each S-box and 4-bit data is output therefrom and so that 32-bit output data is obtained in all. The 32-bit output data is converted into other 32-bit data by the P transposition and then an XOR thereof with the input data L15 is calculated to yield one piece of the output data L16. The other piece of the output data R16 is the direct output of the input data R15.
In such data conversion processing, data unknown to potential attackers is only the 48-bit key data K16. Potential attackers determine the 48-bit value by analyzing the power consumption of the DES cryptographic device performing the 16-th data conversion processing.
More specifically, potential attackers collect power consumption waveforms vi (t) in DES processing of 1000 samples. t denotes discrete values of time and i denotes the sample number (0≦i≦999).
One bit of output of some S-box s in the 16-th stage is defined as a target bit. Six-bit input data c of the S-box s can be derived by retracing the output data L16. The input data c of the S-box s includes, in addition to the input data c, a 6-bit partial key kj to be XORed with the input data c. The S-box output one bit to be the target is written as si (kj, ci) with the partial key kj set as an unknown variable.
Based on the collected power consumption waveform, a differential average trace Tj (t) is calculated by the formula below:
                                          T            j                    ⁡                      (            t            )                          =                              ∑                          i              =              0                        999                    ⁢                                    (                                                                    s                    i                                    ⁡                                      (                                                                  k                        j                                            ,                                              c                        i                                                              )                                                  -                                  1                  2                                            )                        ⁢                                          v                i                            ⁡                              (                t                )                                                                        [                  Math          ⁢                                          ⁢          1                ]            
If the differential average trace Tj (t) is calculated for all cases of 64 combinations as the 6-bit partial key kj, one partial key kj of 64 combinations matches the partial key kj actually used and the differential average trace Tj (t) in that case indicates the deviation of value. For partial keys of other 63 combinations, the partial average trace Tj (t) does not deviate. Based on these deviation characteristics, the 6-bit partial key kj can be identified.
By applying this operation to the other seven S-boxes s, the 48-bit key data K16 can be found.
In such a power analysis, the fact that there is a correlation between the value of the unknown variable kj anticipated by potential attackers and the power consumption vi (t) works. This also applies to the timing analysis involving the correlation between values of unknown variables and the measurement time.
Thus, if conversely such a correlation is eliminated, leakage of secret information through side channel analysis can be prevented. Therefore, a technique to mask random numbers in data processed by a cryptographic device is known to eliminate the correlation between data processed by the cryptographic device and data anticipated by potential attackers.
Mainly two kinds of masks, a logical mask and an arithmetic mask, are known as mask methods and which mask to use is decided based on operations constituting a cryptographic algorithm. For example, the logical mask is used for a cryptographic algorithm composed of logical operations and the arithmetic mask is used for a cryptographic algorithm composed of arithmetic operations. It is more efficient to make an operation used for masking and an operation of a cryptographic algorithm commutable. That is, when an operation of a cryptographic algorithm is performed on masked data, the operation is defined in such a way that an operation result after the last unmasking is the same as an operation result obtained when masking is not used from the start. Generally, secret key cryptography frequently uses the logical mask and the public key cryptography frequently uses the arithmetic mask.
There exist some algorithms in secret key cryptographic systems and hash functions that use both a logical operation and an arithmetic operation in one algorithm. In secret key cryptographic systems, such an algorithm is contained in IDEA (International Data Encryption Algorithm) and Seed. In hash functions, such an algorithm is contained in SHA-1 (Secure Hash Algorithm-1). To mask data in such algorithms, it is necessary to use the logical mask in a portion using a logical operation of a cryptographic algorithm and the arithmetic mask in a portion using an arithmetic operation.
In these algorithms, if the processing unit (word) is w bits, an operation of the following formula is performed to mask w-bit data x by a w-bit number R by using an XOR for the logical mask:x′=x^R (^ is a symbol representing an XOR)
For the arithmetic mask, an operation of the following formula is performed by using a modular subtraction:A=x−R mod 2w 
In the examples of the above cryptographic algorithms, w=32 bits.
Therefore, in a situation changing from a logical operation to an arithmetic operation in an operation sequence of a cryptographic algorithm, it is necessary to convert data from data that is logically masked (hereinafter, referred to as logically masked data) x′ to data that is arithmetically masked (hereinafter, referred to as arithmetically masked data) A. Similarly, in a situation changing from an arithmetic operation to a logical operation, it is necessary to convert data from the arithmetically masked data A to the logically masked data x′.
For example, the simplest method of converting the logically masked data x′ into the arithmetically masked data A is a scheme of operating (x′^R)−R mod 2w. However, this scheme is not desirable because x′^R=x and so unmasked data appears during operation.
As methods of converting the logically masked data x′ and the arithmetically masked data A while data is always masked, L. Goubin, “A Sound Method for Switching Between Boolean and Arithmetic Masking”, CHES 2001, LNCS 2162, pp. 3-15, 2001 (hereinafter, called the [Goubin2001] method) and J-S. Coron, A. Tchulkine, “A New Algorithm for Switching from Arithmetic to Boolean Masking”, CHES 2003, LNCS 2779, pp. 89-97, 2003 (hereinafter, called the [CT2003] method) are known. The [Goubin2001] method proposes a method of converting the logically masked data x′ into the arithmetically masked data A and a method of converting the arithmetically masked data A into the logically masked data x′. The latter method is less efficient and the [CT2003] method that seeks to achieve speed enhancement by using a pre-calculated table is proposed.
The method of converting the arithmetically masked data A into the logically masked data x′ in the [CT2003] method will be described using FIGS. 8 to 10. The unit in which operations are performed is assumed to be b bits. For the sake of simplicity, b is assumed to be a divisor of w and can be expressed as w=k×b using an integer k.
First, a pre-calculated table G is constructed when the logical mask and the arithmetic mask are in b bits (that is, w=b, k=1). The pre-calculated table is defined by the formula below for each integer from 0 to 2b−1:G[I]=((I+r)mod 2b)^r 
For the sake of convenience, a b-bit random number is denoted as r. If w=b, r is related with the number R by R=r. The pre-calculated table G is a table composed of 2b pieces of element data and each piece of element data is b-bit data. The arithmetically masked data A can be converted into the logically masked data x′ by determining the element data G[A] of the pre-calculated table G. The reason is as follows:
                              G          ⁡                      [            A            ]                          =                ⁢                              (                                          (                                  A                  +                  r                                )                            ⁢              mod              ⁢                                                          ⁢                              2                b                                      )                    ^          r                                        =                ⁢                              (                                          (                                  x                  -                  r                                )                            +                              r                ⁢                                                                  ⁢                mod                ⁢                                                                  ⁢                                  2                  w                                                      )                    ^          r                                        =                ⁢                              (                          x              ⁢                                                          ⁢              mod              ⁢                                                          ⁢                              2                w                                      )                    ^          r                                        =                ⁢                  x          ^          r                                        =                ⁢                  x          ′                    
FIG. 8 shows the pre-calculated table G when w=b=4 and r=3. The array in FIG. 8 shows values of G[0], G[1], . . . , G[15] from the left in hexadecimal notation. For example, G[9]=0xF.
FIG. 9 shows an algorithm to convert the arithmetically masked data A into the logically masked data x′ by the [CT2003] method. The algorithm is an algorithm that outputs, when the arithmetically masked data A in w=k×b bits and the number R are input, the logically masked data x′ in w bits.
First, an integer m and the logically masked data x′ are set as m=k and x′=0 (steps S110, 120).
Next, the random number r is subtracted from the arithmetically masked data A under mod 2mb (step S130).
The number R is divided into an upper number R1 and a lower number R2 at the b-th bit number from LSB (Least Significant Bit) (step S140). That is, the upper number R1 is composed of the upper (m−1)b bits of the number R and the lower number R2 is composed of the lower b bits.
The lower number R2 is added to the arithmetically masked data A under mod 2mb (step S150).
Next, for an integer m, whether m=1 is determined (step S160). If m=1, logically masked upper data x′1 is calculated by the formula below (steps S170, S180):x′1=(G[A]^R2)^r 
Subsequently, the obtained logically masked upper data x′1 is arranged in the most significant b bits of the logically masked data x′ (step S190) before terminating the algorithm.
If m>1, processing below is performed.
The arithmetically masked data A is divided, like the number R, into arithmetically masked upper data A1 and arithmetically masked lower data A2 (step S161).
To relate carrying-over (the (b+1)-th bit value caused by A2+r) in step S130 and step S150 to the arithmetically masked upper data A1, the formula below is calculated (steps S162, S163). “Carrying-over” herein may be replaced with “carry”.A1=(A1+C[A2])−γ mod 2(m−1)b 
Subsequently, logically masked lower data x′2 is calculated by the formula below (steps S164, S165).x′2=(G[A2]^R2)^r 
Subsequently, the logically masked lower data x′2 is arranged in such a way that the least significant bit LSB of the logically masked lower data x′2 is aligned with the lower (k−m)b-th bit of the logically masked data x′ (step S166).
Subsequently, the integer m is updated to m=m−1 (step S167) to repeat from step S130.
When carrying-over (carry) from lower digits is adjusted in step S130 and step S150 in the above algorithm, a pre-calculated table C and the b-bit random number γ are used to mask the carrying-over information. The pre-calculated table C is defined for each integer I from 0 to 2b−1 as follows:C[I]=γ (when I+r<2b)C[I]=γ+1 (when I+r≧2b)
The pre-calculated table C is a table composed of 2b pieces of element data and each piece of element data is b-bit data.
FIG. 10 shows the pre-calculated table C when b=4, r=3, and γ=9. The array in FIG. 10 shows values of C[0], C[1], . . . , C[15] from the left in hexadecimal notation. For example, C[0xE]=0xA.